#ifndef Input_CPP
#define Input_CPP

#include<fstream>
#include<limits>
#include<ctime>
#include<cstdlib>
#include<time.h>

void processInput (char* input, unsigned int* vertex1, unsigned int* vertex2, unsigned int* cost);
unsigned int parseInt (char* input);
bool traverseGraphDFS(unsigned int** cost, int arrSize);

void randomInput(AdjacencyList* list)
{
    bool connected = false;
    AllSSPBinomial* bHeapScheme = new AllSSPBinomial();
    AllSSPFibonacci* fHeapScheme = new AllSSPFibonacci();
    AllSSPSimple* simpleScheme = new AllSSPSimple();

    int numberOfNodesArr[] = {100, 200, 300, 400, 500};
    int densityArr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    clock_t totalSimple, totalBHeap, totalFHeap, startSimple, startBHeap, startFHeap, timeSimple, timeBHeap, timeFHeap;
    printf("Nodes          Density(%%)     Simple(msecs)  F-Heap(msecs)  B-Heap(msecs)\n");
    //cout<<"Nodes\t\tDensity(%)\tSimple\t\tB-Heap\t\tF-Heap\n";
    for(int i=0; i<5; i++)
    {
        int numberOfNodes = numberOfNodesArr[i];
        for (int j=0; j<10; j++)
        {
            int density = densityArr[j];
            printf ("%-15d%-15d", numberOfNodes, density);
            totalSimple = totalBHeap = totalFHeap = 0;

            //generating a weakly connected random graph
            do
            {
                srand (time(NULL));
                list->emptyIt();
                unsigned int minCostVertex = std::numeric_limits<unsigned int>::max();;
                for (int i=0; i < numberOfNodes*(numberOfNodes-1)*density/100; )
                {
                    unsigned int vertex1 = rand() % numberOfNodes;
                    unsigned int vertex2 = 0;
                    do
                    {
                        vertex2 = rand() % numberOfNodes;
                    } while (vertex1 == vertex2);
                    unsigned int edgeCost = (rand() % 1000) + 1;
                    if (list->addEdge(vertex1, vertex2, edgeCost))
                    {
                        if (minCostVertex > edgeCost)
                        {
                            minCostVertex = edgeCost;
                        }
                        i++;
                    }
                }
                connected = traverseGraphDFS(list->getUndirectedGraphCostMatrix(numberOfNodes), numberOfNodes);
            } while (!connected);
            for (int k=0; k<5; k++)
            {
                //Case 1: simple scheme
                simpleScheme->init(list);
                startSimple = clock();
                simpleScheme->computeShortestPath();
                timeSimple = clock() - startSimple;
                totalSimple += timeSimple;

                //case 2: Binomial Heap way
                bHeapScheme->init(list);
                startBHeap = clock();
                bHeapScheme->computeShortestPath();
                timeBHeap = clock() - startBHeap;
                totalBHeap += timeBHeap;
                bHeapScheme->deleteDistMatrix();

                //case 3: Fibonacci Heap way
                fHeapScheme->init(list);
                startFHeap = clock();
                fHeapScheme->computeShortestPath();
                timeFHeap = clock() - startFHeap;
                totalFHeap += timeFHeap;
                fHeapScheme->DeleteDistMatrix();
            }
            printf ("%-15f%-15f%-15f\n", ((float)totalSimple/5)/CLOCKS_PER_SEC*1000, ((float)totalFHeap/5)/CLOCKS_PER_SEC*1000, ((float)totalBHeap/5)/CLOCKS_PER_SEC*1000);
        }
    }
    delete (bHeapScheme);
    delete (fHeapScheme);
    cout<<"done";
}

bool traverseGraphDFS(unsigned int** cost, int arrSize)
{
    bool* visited = new bool[arrSize];
    for (int i=0; i<arrSize; i++)
    {
        visited[i] = false;
    }
    int* startNode = new int();
    *startNode = 0;
    Queue<int> adjNodes;
    adjNodes.enqueue(startNode);
    visited[*startNode] = true;
    int* node;
    int count = 1;
    while ((node = adjNodes.dequeue()) != NULL)
    {
        for (int i=0; i<arrSize; i++)
        {
            if (cost[*node][i] != std::numeric_limits<unsigned int>::max() && !visited[i])
            {
                adjNodes.enqueue(new int(i));
                visited[i] = true;
                count++;
                if (count == arrSize)
                {
                    break;
                }
            }
        }
    }
    for (int i=0; i<arrSize; i++)
    {
        delete[] cost[i];
    }
    delete[] cost;
    if (count == arrSize)
    {
        return true;
    }
    return false;
}

void interactiveUserInput(AdjacencyList* list)
{
    cout<<"\nInteractive User Input\n";
    cout << "\nEnter edges <V1 V2 C>\n\n";
    while (true)
    {
        unsigned int vertex1_uint, vertex2_uint, cost_uint;
        char vertex1[10], vertex2[10], cost[10];
        cin>>vertex1;
        if (vertex1[0] == '*')
        {
            break;
        }
        vertex1_uint = parseInt(vertex1);

        cin>>vertex2;
        if (vertex2[0] == '*')
        {
            cout<< "\nInput Error.. Reading next edge after * as start vertex..\n";
            continue;
        }
        vertex2_uint = parseInt(vertex2);

        cin>>cost;
        if (cost[0] == '*')
        {
            cout<< "\nInput Error.. Reading next edge after * as start vertex..\n";
            continue;
        }
        cost_uint = parseInt(cost);
        list->addEdge(vertex1_uint, vertex2_uint, cost_uint);
    }
}

void fileInput(char* fileName, AdjacencyList* list)
{
    cout<<"\nFile Input";
    ifstream inputStream;
    inputStream.open (fileName);

    while (!inputStream.eof())
    {
        unsigned int vertex1_uint, vertex2_uint, cost_uint;
        char vertex1[10], vertex2[10], cost[10];
        inputStream>>vertex1;
        if (vertex1[0] == '*')
        {
            break;
        }
        vertex1_uint = parseInt(vertex1);

        inputStream>>vertex2;
        if (vertex2[0] == '*')
        {
            cout<< "\nInput Error.. Ignoring.. Reading next element as vertex1\n";
            continue;
        }
        vertex2_uint = parseInt(vertex2);

        inputStream>>cost;
        if (cost[0] == '*')
        {
            cout<< "\nInput Error.. Ignoring.. Reading next element as vertex1\n";
            continue;
        }
        cost_uint = parseInt(cost);
        list->addEdge(vertex1_uint, vertex2_uint, cost_uint);
    }
}

unsigned int parseInt (char* input)
{
    int count = 0;
    while (!(input[count] >= '0' && input[count] <= '9'))
    {
        count++;
    } //ignoring initial spaces
    unsigned int num = 0;
    while (input[count] >= '0' && input[count] <= '9')
    {
        num = num*10 + ((int)input[count] - (int)'0');
        count++;
    }
    return num;
}

void processInput (char* input, unsigned int* vertex1, unsigned int* vertex2, unsigned int* cost)
{
    int swIndex = 0;
    int count = 0;
    while (swIndex < 3)
    {
        int num = 0;
        while (!(input[count] >= '0' && input[count] <= '9'))
        {
            count++;
        } //ignoring initial spaces
        while (input[count] >= '0' && input[count] <= '9')
        {
            num = num*10 + ((int)input[count] - (int)'0');
            count++;
        }
        cout<<"swIndex: "<<swIndex<<"  number: "<<num;
        switch (swIndex)
        {
        case 0: *vertex1 = num;
            break;
        case 1: *vertex2 = num;
            break;
        case 2: *cost = num;
        }
        swIndex++;
    }
}

#endif